package sword.chapter7Queue;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 二叉树每层的最大值
 *
 * 广度优先搜索 双队列
 * curQueue     当前层节点队列
 * nextQueue    下一层节点队列
 *
 * curQueue遍历完后，重新指向nextQueue，result添加当前层节点最大值，nextQueue重新赋值
 *
 * @author K
 * @date 2021/12/6 09:12
 */
public class S44LargestValues {

    /**
     * 双队列
     */
    public static List<Integer> s44(TreeNode root) {
        LinkedList<Integer> result = new LinkedList<>();
        int max = Integer.MIN_VALUE;
        Queue<TreeNode> curQueue = new LinkedList<>();
        Queue<TreeNode> nextQueue = new LinkedList<>();
        curQueue.offer(root);
        while (!curQueue.isEmpty()) {
            TreeNode node = curQueue.poll();
            max = Math.max(max, node.val);
            if (node.left != null) {
                nextQueue.offer(node.left);
            }
            if (node.right != null) {
                nextQueue.offer(node.right);
            }
            if (curQueue.isEmpty()) {
                result.add(max);
                max = Integer.MIN_VALUE;
                curQueue = nextQueue;
                nextQueue = new LinkedList<>();
            }
        }

        return result;
    }

    /**
     * 单队列
     * 思路与双队列一样
     */
    public static List<Integer> s44A(TreeNode root) {
        int current = 0;
        int next = 0;
        LinkedList<Integer> result = new LinkedList<>();
        int max = Integer.MIN_VALUE;
        Queue<TreeNode> curQueue = new LinkedList<>();
        curQueue.offer(root);
        current = 1;

        while (!curQueue.isEmpty()) {
            TreeNode node = curQueue.poll();
            current--;
            max = Math.max(max, node.val);
            if (node.left != null) {
                curQueue.offer(node.left);
                next++;
            }
            if (node.right != null) {
                curQueue.offer(node.right);
                next++;
            }
            // 当前层节点全部遍历完，重新赋值
            if (current == 0) {
                result.add(max);
                current = next;
                next = 0;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        root.left = node2;
        root.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;

        List<Integer> result = s44(root);
        List<Integer> result2 = s44A(root);
        System.out.println();
    }


}
